package leetcode_1701_1800;


import java.util.HashMap;
import java.util.Map;

public class LeeCode_1711 {
    public static void main(String[] args) {
        System.out.println(countPairs(new int[]{1, 3, 5, 7, 9}));
    }
    private static int countPairs(int[] deliciousness) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : deliciousness) {
            map.put(i, map.getOrDefault(i, 0) + 1);
        }
        long ans = 0, mod = (long) (1e9 + 7), max = 1 << 22;
        for (Integer n1 : map.keySet()) {
            for (int i = 1; i < max; i <<= 1) {
                int n2 = i - n1;
                if (map.containsKey(n2)){
                    if (n1 == n2){
                        ans += (long) map.get(n1) * (map.get(n1) - 1);
                    }else {
                        ans += (long) map.get(n1) * map.get(n2);
                    }
                }
            }
        }
        ans >>>= 1;
        return (int) (ans % mod);
    }
}
